#pragma once

#include <vector>
#include <algorithm>

using namespace std;

void InsertSort(vector<int>& v)
{
  int n = v.size();
  for(int i = 1; i < n; ++i)
  {
    int end = i;
    int endEle = v[end];
    while(end -1 >= 0 && endEle < v[end - 1])
    {
      v[end] = v[end - 1];
      --end;
    }
    v[end] = endEle;
  }
}

int getMidI(vector<int>& v, int begin ,int end)
{
  int mid = begin + (end - begin) / 2;
  int maxEleI = begin;
  if(v[mid] > v[maxEleI]) { maxEleI = mid; }
  if(v[end] > v[maxEleI]) { maxEleI = end; }
  int minEleI = begin;
  if(v[mid] < v[minEleI]) { minEleI = mid; }
  if(v[end] < v[minEleI]) { minEleI = end; }
  int midI = begin + end + mid - maxEleI - minEleI;
  return midI;
}

void QuickSort(vector<int>& v,  int begin, int end)
{
     if(begin >= end) { return; }
     int midI = getMidI(v, begin, end);
     swap(v[begin], v[midI]);
     int key = v[begin];
     int left = begin, right = end;
     while(left < right)
     {
       while(left < right && v[right] >= key) { --right; }
       while(left < right && v[left] <= key) {++left;}
       swap(v[left], v[right]);
     }
     swap(v[begin], v[left]);
     int keyi = left;
     QuickSort(v, begin, keyi - 1);
     QuickSort(v, keyi + 1, end);
}
